Definition

Given a strictly convex function hh, may define a distance function based on how the function differs from its linear approximation:

The Bregman divergence from xx to yy with respect to function hh is

Dh(y‖x):=h(y)−h(x)−⟨∇h(x),y−x⟩D_h(y \Vert x) := h(y) - h(x) - \langle \nabla h(x), y-x \rangle

The function hh may be called the distance-generating function (DGF) for the divergence.

Notes

e.g. for a function h:ℝ→ℝh : \mathbb{R} \to \mathbb{R}
300
(intuition: h(x)+⟨∇h(x),y−x⟩h(x) + \langle \nabla h(x), y-x \rangle would be the linear approximation)

References

  1. https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15850-f20/www/notes/lec19.pdf
  2. https://www.mit.edu/~gfarina/2025/67220s25_L14_mirror_descent/
  3. https://www.mit.edu/~gfarina/2024/67220s24_L18_omd/L18.pdf
  4. http://www.lamda.nju.edu.cn/zhaop/course/AOpt2023fall/Lecture7_OnlineMirrorDescent.pdf